/*
 * 2.5
 * Given a circular linked list, implement an algorithm which returns node at the begin-
 * ning of the loop.
 * DEFINITION
 * Circular linked list: A (corrupt) linked list in which a node’s next pointer points to an
 * earlier node, so as to make a loop in the linked list.
 * EXAMPLE
 * input: A -> B -> C -> D -> E -> C [the same C as earlier]
 * output: C
 */
#include <stdio.h>
#include <stdlib.h>

typedef struct _node_t {
    int v;
    struct _node_t *next;
} node_t;

node_t *find_loop_begin(node_t *head)
{
    node_t *fast = head, *slow = head;
    while (fast) {
        fast = fast->next;
        if (!fast) {
            break;
        } else {
            fast = fast->next;
        }
        slow = slow->next;
        if (fast == slow) {
            break;
        }
    }
    /* check */
    if (!fast) {
        return NULL;
    }
    slow = head;
    while (fast && slow) {
        if (fast == slow) {
            return fast;
        }
        fast = fast->next;
        slow = slow->next;
    }
    return NULL;
}

node_t *new_node(int v)
{
    node_t *node = (node_t *)malloc(sizeof(node_t));
    node->v = v;
    return node;
}

int main()
{
    node_t *head = new_node(0);
    node_t *curr, *prev;
    int i = 1;
    prev = head;
    while (i < 7) {
        curr = new_node(i);
        prev->next = curr;
        prev = curr;
        i++;
    }
    /* add a loop */
    curr->next = head->next->next->next;
    node_t *find = find_loop_begin(head);
    printf("find loop = %d\n", find ? find->v : -1);
    /* free */
    bool once = false;
    prev = head;
    while (prev) {
        if (prev == find) {
            if (once) {
                break;
            }
            once = true;
        }
        curr = prev->next;
        free(prev);
        prev = curr;
    }
}
